#include <bits/stdc++.h>

using namespace std;

const int maxn=100005;
int a[maxn];
long long b[maxn];
long long s[maxn];

int main(){
    int T,n,i;
    long long sum,ans;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        sum=0;
        for(i=0;i<n;i++) scanf("%d",a+i),i?s[i]=a[i]+s[i-1]:s[i]=a[i];
        sort(a,a+n);
        for(int N=1;N<=n;N++){
            ans=0;
            int nn=N;
            sum+=a[N-1];
            for(i=2;i<=nn;i<<=1) ans+=sum;
            i>>=1;
            nn-=i;
            nn*=2;
            ans+=s[nn-1];
            b[N]=ans;
        }
        for(int i=2;i<=n;i++) b[n]=min(b[n],b[n-1]+s[n-2]+a[n-1]);
        printf("%lld\n",b[n]);
    }
}
